package bin_tree.leetcode;

/**
 * 找最近公共祖先
 **/
public class Num236 {
    // 最近公共祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 找到p和q的所有祖先
        findNode(root,p,q);
        return lca;
    }

    /**
     * 以当前root为根节点的二叉树能否找到节点p或q
     * @param root
     * @param p
     * @param q
     */
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int left = findNode(root.left,p,q) ? 1 : 0;
        int right = findNode(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + mid + right == 2) {
            lca = root;
        }
        return (left + mid + right) > 0;
    }
}